#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct listnode
{
    int val;
    struct listnode * next;
}Node;

// --struction a node and return the node
static Node * Node_construct(int val){

    Node * node = malloc(sizeof(Node));
    // -check
    if(NULL == node){

        printf("malloc node failed.\n");
        return NULL;
    }
    node->val = val;
    node->next = NULL;
    return node;
}
// --insert node and become the head of the linklist 
static Node * List_insert(Node * head,int val){

    Node * node = Node_construct(val);
    if(NULL == node){

        return head;
    }
    // -pointer next node
    node->next = head;
    return node;
}

// --remove item by the val and return the head node
static Node * List_delete(Node * head,int val){

    // -if no check the program will crash
    if(NULL == head){

        return NULL;
    }
    if(val == head->val){

        Node * ptr = head;
        head = head->next;
        free(ptr);
        return head;
    }
    // -no use no declare
    Node * prevNode = head;
    Node * nextNode = head->next;
    while(nextNode && nextNode->val!=val){

        prevNode = prevNode->next;
        nextNode = nextNode->next;
    }
    // -found val
    if(NULL != nextNode){

        prevNode->next = nextNode->next;
        free(nextNode);
    } 
    // -maybe it is null
    return head;
}

// --print item
static void List_print(Node * head){

    Node * ptr = head;
    while (NULL != ptr)
    {
        printf("%d ",ptr->val);
        ptr = ptr->next;
    }
    printf(".\n\n");
}

// -递归函数
static void List_print2Help(Node * head){

    if(NULL == head){

        return;
    }
    printf("%d ",head->val);
    List_print2Help(head->next);
}

static void List_print2(Node * head){

    printf("\nPrint the whole list:\n");
    List_print2Help(head);
    printf("\n\n");
}

void List_destory(Node * head){

    while(NULL!=head){

        Node * freeNode = head;
        head = head->next;
        free(freeNode);
    }
}

Node * List_search(Node * head,int val){

    // -must check the head
    if(NULL == head){

        return NULL;
    }
    Node * ptr = head;
    while(ptr && ptr->val!=val){

        ptr = ptr->next;
    }
    // -maybe it is null or node object
    return ptr;
}

// -链表翻转
Node * List_reverse(Node * head){

    if(NULL == head){

        return NULL;
    }
    if(NULL == head->next){

        return head;
    }
    // -revHead指向反转的头节点
    Node * revHead = NULL;
    // -orignHead指向未翻转的头节点
    Node * orignHead = head;
    // -origSecon指向未翻转的第二个节点
    Node * origSecon = head->next;

    while(orignHead){

        orignHead->next = revHead;
        revHead = orignHead;
        orignHead = origSecon;
        if(NULL == orignHead){

            break;
        }
        origSecon = origSecon->next;
    }
    return revHead;
}
// -递归版本
void List_reverse(Node * head){


}

Node * List_reverseHelp(Node * first,Node * second){

    if(NULL == second->next){

        second->next = first;
        return first;
    }
    Node * t = List_reverseHelp(first->next,second->next);
    t->next = first;
    return first;
}


int main(int argc,char * argv[]){

    Node * head = NULL;
    head = List_insert(head,917);
    head = List_insert(head,-504);
    head = List_insert(head,326);
    head = List_insert(head,328);
    head = List_insert(head,356);
    head = List_insert(head,336);

    List_print(head);

    if(NULL!=List_search(head,138)){

        printf("138 is in the list.\n");
    }else{

        printf("138 is not in the lits.\n");
    }
    if(NULL!=List_search(head,987)){

        printf("987 is int the list.\n");
    }else{

        printf("987 is not in the list.\n");
    }
    List_print(head);
    head = List_reverse(head);
    List_print(head);

    head = List_delete(head,263);
    List_print(head);
    head = List_delete(head,917);
    List_print(head);
    List_destory(head);
    return EXIT_SUCCESS;
}